1. Technical Field
The present invention relates generally to computer graphics, and more particularly to a method for reducing page switches when rendering polygons in a frame buffer comprising multiple banks of memory.
2. Description of the Prior Art
The implementation of 3D graphics is a computationally intensive operation involving multiple processing stages in dedicated graphics rendering hardware, commonly referred to as "graphics engines" or "graphics accelerators". Most of the complex operations in the graphics engine are performed on the pixel level. Some of the more complex operations performed by the graphics engines include anti-aliasing, trilinear interpolation, and z-buffering. These and other advanced 3D rendering techniques greatly enhance the level of realism in 3D imagery. Rendering a display scene to an observer involves taking a three-dimensional model of some area of the world which consists of multiple 3D objects. The objects are typically stored in a data base as a composite of polygons. An image generator would read in each 3D object, polygon by polygon, and transform it into a 2D scene description. The 2D scene description is ultimately converted to analog video which is presented to a user on a display device. Given a set of 3D objects and a viewing specification, a determination must be made concerning which lines or surfaces of the objects are visible so that only visible lines and surfaces are displayed. The z-buffer or depth-buffer algorithm is one of the simplest and widely utilized visible-surface algorithms available to perform this task. The z-buffer algorithm serves to maintain the correct perspective between objects which are closer to a viewpoint than others. The largest value that can be stored in the z-buffer represents that value associated with the distance closest to the current projection plane. When a new polygon is being rendered, the rendering engine compares the z-values of its vertices to the previously stored z-value in the same (x,y) location in the z-buffer. The previously stored z-value would have been associated with a previously rendered polygon.
To perform z-buffering a frame buffer is required that consists of memory subsystems capable of storing pixel data associated with color and depth values. Color values would be stored in a color buffer memory subsystem and depth values in a z-buffer memory subsystem. The computation of the z-value is well known in the prior art and is computed by plugging the (x,y) pixel value pair into the plane equation for the polygon. If the new point, associated with the polygon being processed, has a z value greater than the previous one (i.e closer to the projection plane), its z-value is placed in the z-buffer, replacing the previous z-value; otherwise the previous z-value remains in the z-buffer. Therefore, z-buffer processing in its most general description involves reading from a z-buffer, comparing the value read to a value associated with the polygon currently being processed and possibly overwriting the current z-buffer value with the new value. In those situations where a z-buffer value is to be overwritten a corresponding overwrite will occur to the color buffer.
The color buffer and z-buffer are each organized as a series of contiguous pages in the frame buffer where each page defines a fixed number of storage positions associated with some number of pixels in the display device. As an example of how frame buffer pages define pixels in a raster display, typical line rendering systems associate the storage locations of a single frame buffer page to approximately one and one-quarter horizontal scan lines of a raster display device. As each polygon is processed by the graphics engine, color and z-buffer memory pages of the frame buffer are accessed to either read or write pixel data. A page switch occurs whenever a page in the frame buffer memory is accessed to perform a read/write, where the page index of the accessed page is different from the index of the page most recently accessed. The newly accessed page is said to be activated. An undesirable overhead cost of some fixed number of clock cycles is incurred whenever a page switch occurs and a new page is activated. The cost becomes significant when performing z-buffering in either a tile or linear address rendering system when in the performance of the z-buffering algorithm the color and z-buffers are written to in immediate succession. In contrast, successive read/writes to the same buffer, such as z or color, are coherent and result in no page switches.
For the above reasons, there is a need in the art for a simple method for reducing the number of page switches when rendering polygons to a color and Z buffer using a memory subsystem that has multiple banks of memory.